#ifndef PRIME_FACTORIZATION_HPP
#define PRIME_FACTORIZATION_HPP

#include<vector>
#include<cmath>
#include <iostream>

class PrimeFactorization{
    const static int primes[];
    const static int N;
public:
    static void small_prime_factorize(std::vector<int> & result, int n){
        result.clear();
        if ( n == 0 ){
            result.push_back( 0 );
            return;
        }
        if ( n == 1 ){
            result.push_back( 1 );
            return;
        }

        //int n_saved = n;
        //int m = sqrt( n );
        for( int i= 0; i < N; ++i ){
            int p = primes[i];
            if ( n == 1 || n < p){
                break;
            }
            while( n % p == 0 ){
                n /= p;
                result.push_back( p );
            }
        }
        if ( n != 1 ){
            result.push_back( n );
            //std::cout << "number " << n_saved << " is not factorized!!!" << std::endl;
        }
    }
};

const int PrimeFactorization::primes [] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167};
const int PrimeFactorization::N = sizeof(PrimeFactorization::primes)/sizeof(int);

class Partition{

    std::vector<int> proc_primes_;
    std::vector<int> cur_result_;
    double ratio_;

    std::vector<int> best_result_;
    double best_ratio_;

    void partition_recurse( int n, int m, size_t depth, int cur_product_n, int cur_product_m ){
        if ( depth < proc_primes_.size() ){
            int c = proc_primes_.at( depth );
            int product_n = cur_product_n * c;
            partition_recurse( n, m, depth + 1, product_n, cur_product_m );
            cur_result_.push_back( c );
            int product_m = cur_product_m * c;
            partition_recurse( n, m, depth + 1, cur_product_n, product_m );
            cur_result_.pop_back();
        }else{
            double ratio = ((double)cur_product_n) / cur_product_m;
            //std::cout << ratio_ << " | " << ratio << " | " << best_ratio_ << " | "<< std::abs( ratio_ - ratio ) << " | " << std::abs(ratio_ - best_ratio_) << std::endl;
            if ( std::abs(ratio_ - ratio ) <  std::abs(ratio_ - best_ratio_) ){
                //std::cout << "hit" << std::endl;
                best_result_ = cur_result_;
                best_ratio_ = ratio;
            }
            //std::cout << abs( ratio_ - ratio ) << " | " << abs(ratio_ - best_ratio_) << std::endl;
            //for( size_t i = 0; i < cur_result_.size(); ++i ){
            //    std::cout << cur_result_[i] << " ";
            //}
            //std::cout << std::endl;
            //std::cout << cur_product_m << " : " << cur_product_n << std::endl;
            //std::cout << "-------------" << std::endl;
        }
    }

public:
    void partition(int p, int n, int m, int * n_dim, int * m_dim ){
        PrimeFactorization::small_prime_factorize( proc_primes_, p );
        ratio_ = ((double) n) / m;

        best_ratio_ = p / 1.0;
        partition_recurse( n, m, 0, 1, 1);

        int k = 1;
        for( size_t t = 0; t <  best_result_.size(); ++t){
            int r = best_result_[t];
            //std::cout << r << " ";
            k  *= r;
        }
        *n_dim = p / k;
        *m_dim =  k;
        std::cout << "n x m : " << *n_dim << " x "<< *m_dim << std::endl;
    }
};

#endif // PRIME_FACTORIZATION_HPP
